package com.qch.edu.Tree.excise;

/**
 * @Author qch
 * @Date 2021/3/13
 * 后继节点，中序遍历下左头右
 * 找x的后继
 * 如果h是最左节点，那向上找父节点，及时它的后继节点
 * 如果h是最右节点，那向上找父节点，我是父节点的右孩子继续往上，直到成为那个节点的左孩子，则，该节点为后继节点（如一直往上都没有找到作为左孩子的父节点，返回为空就可）
 */
public class NextNodeTree {
    public static class Node {
        private int value;        //节点的值
        private Node node;        //此节点，数据类型为Node
        private Node left;        //此节点的左子节点，数据类型为Node
        private Node right;       //此节点的右子节点，数据类型为Node
        private Node parent;
        public Node(int data){
            this.value=data;
        }
    }
    public static Node getSuccessorNode(Node node){
        if (node == null) {
            return node;
        }
        if (node.right!=null)
        {
            return getLeftMost(node.right);//找右树上的最左节点
        }else {
            //无右子树
            Node parent=node.parent;
            while (parent!=null&&parent.right==node)//当前节点是其父亲几点右孩子
            {
                node=parent;
                parent=node.parent;
            }
            return parent;
        }
    }

    private static Node getLeftMost(Node node) {
        if (node==null){
            return node;
        }
        while (node.left!=null){
            node=node.left;
        }
        return node;
    }

    public static void main(String[] args) {
        Node head=new Node(6);
        head.parent=null;
        head.left=new Node(3);
        head.left.parent=head;
        head.left.left=new Node(1);
        head.left.left.parent=head.left;
        head.left.left.right=new Node(2);
        head.left.left.right.parent= head.left.left;
        head.left.right=new Node(4);
        head.left.right.parent=head.left;
        head.left.right.right=new Node(5);
        head.left.right.parent=head.left.right;
        Node successorNode = getSuccessorNode(head.left.right);
        System.out.println(successorNode.value);
    }
}
